package features.advance.leetcode.geometry.stack.easy;

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

/**
 * 21. 合并两个有序链表
 * 难度  简单
 * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
 *
 *
 *
 * 示例：
 *
 * 输入：1->2->4, 1->3->4
 * 输出：1->1->2->3->4->4
 *
 *
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
public class Solution21 {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        List<Integer> list = new ArrayList<>();
        getAllVal(l1, l2, list);
        if (list.isEmpty()) return null;
        list = list.stream().sorted().collect(Collectors.toList());
        ListNode listNode1 = new ListNode(list.get(list.size() - 1));
        ListNode listNode2;
        for (int i = list.size() - 2; i >= 0; i--) {
            listNode2 = new ListNode(list.get(i), listNode1);
            listNode1 = listNode2;
        }
        return listNode1;
    }

    public List<Integer> getAllVal(ListNode l1, ListNode l2, List<Integer> list){
        if (l1 == null && l2 == null) return null;
        if (l1 != null){
            int val1 = l1.val;
            list.add(val1);
        }
        if (l2 != null){
            int val2 = l2.val;
            list.add(val2);
        }

        return getAllVal(l1==null?l1:l1.next,l2==null?l2:l2.next, list);
    }

    static class ListNode {
        int val;
        ListNode next;
        ListNode() {

        }
        ListNode(int val) {
            this.val = val;
        }
        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public static void main(String[] args) {
        ListNode listNode = new ListNode(1, new Solution21.ListNode(23,new Solution21.ListNode(2)));
        listNode = new ListNode();

        ListNode mergeTwoLists = new Solution21() {
            @Override
            public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

                return super.mergeTwoLists(l1, l2);
            }
        }.mergeTwoLists(null,listNode);

    }
}
